package myStack;

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Stack;

/**
 * 功能描述: 从栈中获取最小值, 使得 pop ,push , getMin的时间复杂度为O(1)
 * 2024/05/23
 * <p>
 * ZhangYi
 */
public class GetMinFromStack02Utils <T>{
    public Stack<T> stack;
    public Stack<T> minStack;

    public Comparator<T> comparator;

    public GetMinFromStack02Utils(Comparator<? super T> comparator)
    {
        this.stack = new Stack<>();
        this.minStack = new Stack<>();
        this.comparator = (Comparator<T>) comparator;
    }

    public void push(T val){
        if (isEmpty()){
            stack.push(val);
            minStack.push(val);
        }else {
            stack.push(val);
            // 比较栈顶元素和最小栈的栈顶元素 如果比栈顶元素小则入栈
            // 否则入栈栈顶元素, 这样就保证了 stack栈中和minStack中的元素个数是一致的
            if (this.comparator.compare(val,minStack.peek())<0){
                minStack.push(val);
            }else {
                minStack.push(minStack.peek());
            }
        }
    }
    public T pop(){
        if (isEmpty()){
            throw new RuntimeException("栈为空");
        }
        T pop = stack.pop();
        minStack.pop();
        return pop;
    }

    public T getMin(){
        if (isEmpty()){
            throw new RuntimeException("栈为空");
        }
        return minStack.peek();
    }
    public boolean isEmpty(){
        return stack.isEmpty() && minStack.isEmpty();
    }

    public static void main(String[] args) {
        GetMinFromStack02Utils<Integer> utils = new GetMinFromStack02Utils<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
            }
        });

        List<Integer> list = Arrays.asList(11, 2, 3, 4, 5, 6, 7, 8, 9, 10);

        for (Integer integer : list) {
            utils.push(integer);
        }
        System.out.println(utils.getMin());
        while (!utils.isEmpty()){
            Integer pop = utils.pop();
            //System.out.println(pop);
        }

        System.out.println("测试完成");
    }
}
